跳转至

并非所有问题都适合建模为 MILP：一种面向 DSL 的灵活且精确的优化建模框架

文章背景与核心概要

组合优化问题（COP）的求解不仅依赖于高效的算法，更依赖于精心设计的数学模型。尽管近期研究已开始利用大语言模型（LLM）实现优化建模的自动化，但现有的主流框架大多局限于混合整数线性规划（MILP）这一范式。本文指出，并非所有问题都适合强制转化为 MILP，因为将复杂的非线性领域强行纳入线性约束往往会导致建模复杂度激增，并严重限制求解器的灵活性。

为了解决这一问题，研究团队提出了 OptiDSL 框架。该框架通过利用 LLM 将自然语言映射为领域特定语言（DSL）表示，实现了问题描述与执行过程的解耦。这种范式转变不仅简化了建模流程，还支持集成包括传统启发式算法和现代学习型方法在内的多种专用求解器，从而在建模精度和效率上取得了显著提升。

核心贡献 (Key Contributions)

  • 范式转变： 从僵化的以 MILP 为中心的建模方法，转向基于 DSL 的灵活表示方法。
  • 解耦架构： 将问题建模与求解器执行分离，支持从传统启发式算法到现代学习型方法等多种算法的灵活调用。
  • 性能提升：
    • 在 44 种 COP 类型的基准测试中，建模准确率提升了 51.66%，建模时间缩短了 91.71%。
    • 相比现有的基于 MILP 的流水线，建模准确率提高了 23.09%。
  • Paradigm Shift: Moves away from the rigid MILP-centric approach toward a flexible, DSL-based representation.
  • Decoupled Architecture: Separates problem formulation from solver execution, enabling the use of diverse algorithms ranging from traditional heuristics to modern learning-based methods.
  • Enhanced Performance:
    • Achieved a 51.66% gain in formulation accuracy and a 91.71% decrease in modeling time across a benchmark of 44 COP types.
    • Demonstrated a 23.09% higher formulation accuracy compared to existing MILP-based pipelines.

摘要 (Abstract)

解决组合优化问题（COP）不仅需要高效的算法，还需要精心构建的数学模型。虽然近期的研究工作已经利用大语言模型（LLM）来实现优化建模的自动化，但当前的框架主要依赖于僵化的混合整数线性规划（MILP）范式。在本文中，我们认为并非所有问题都最适合建模为 MILP，因为将复杂的领域问题强行转化为线性约束可能会导致过高的建模复杂度，并严重限制求解器的灵活性。

为了解决这一问题，我们提出了 OptiDSL，这是一个将重点从僵化的 MILP 建模转向领域特定语言（DSL）表示的框架。通过利用 LLM 将自然语言映射到标准化的、领域公认的结构中，OptiDSL 实现了问题建模与执行的解耦。这种范式使得框架能够与多种专用求解器无缝集成，涵盖了从传统启发式算法到现代学习型方法的广泛范围。

Solving combinatorial optimization problems (COPs) requires not only efficient algorithms but also carefully crafted formulations. While recent works have leveraged LLMs to automate optimization modeling, current frameworks predominantly rely on a rigid mixed-integer linear programming (MILP) paradigm. In this paper, we argue that not all problems are best modeled as MILP, as forcing complex domains into linear constraints can induce prohibitive modeling complexity and severely restrict solver flexibility.

To address this, we propose OptiDSL, a framework that shifts the focus from rigid MILP formulations to domain-specific language (DSL) representations. By utilizing LLMs to map natural language onto standardized, domain-accepted structures, OptiDSL decouples problem formulation from execution. This paradigm enables seamless integration with a diverse library of specialized solvers, ranging from traditional heuristics to modern learning-based methods.

资源 (Resources)